/*
 * @lc app=leetcode.cn id=912 lang=cpp
 *
 * [912] 排序数组
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        ;
    }
};
class SolutionTwoPointer {
public:
    vector<int> sortArray(vector<int>& nums) {
        // 升序排列
        // sort(nums.begin(), nums.end());
        quickSort(0, nums.size()-1,nums);
        return nums;
    }
private:
    int leftPointer_;
    int rightPointer_;
    void quickSort(int left, int right, vector<int>& nums){
        leftPointer_ = left;
        rightPointer_ = right;

        bool goLeft = true;

        while (leftPointer_ != rightPointer_){
            if (goLeft){
                quickGoLeft(leftPointer_, rightPointer_, nums);
            }else{
                quickGoRight(leftPointer_, rightPointer_, nums);
            }
            goLeft = !goLeft;
        }

        int middle = leftPointer_;

        if (middle > left){
            quickSort(left, middle-1, nums);
        }
        if (middle < right){
            quickSort(middle+1, right, nums);
        }
    }
    void quickGoLeft(int& left, int& right, vector<int>& nums){
        // from right, go left
        while (right > left){
            if (nums[right] < nums[left]){
                mySwap(right, left, nums);
                left++;
                break;
            }
            right--;
        }
    }
    void quickGoRight(int& left, int& right, vector<int>& nums){
        // from left, go right
        while (left < right){
            if (nums[left] > nums[right]){
                mySwap(right, left, nums);
                right--;
                break;
            }
            left++;
        }
    }
    void mySwap(int a, int b, vector<int>& nums){
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
};
// @lc code=end

int main(){
    // vector<int> nums = {5, 2, 4, 1};
    vector<int> nums = {5,9,3,0,4,8,1,7,10,6,2};
    Solution test;
    test.sortArray(nums);
}

class Solution {
    int partition(vector<int>& nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[i + 1], nums[r]);
        return i + 1;
    }
    int randomized_partition(vector<int>& nums, int l, int r) {
        int i = rand() % (r - l + 1) + l; // 随机选一个作为我们的主元
        swap(nums[r], nums[i]);
        return partition(nums, l, r);
    }
    void randomized_quicksort(vector<int>& nums, int l, int r) {
        if (l < r) {
            int pos = randomized_partition(nums, l, r);
            randomized_quicksort(nums, l, pos - 1);
            randomized_quicksort(nums, pos + 1, r);
        }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        srand((unsigned)time(NULL));
        randomized_quicksort(nums, 0, (int)nums.size() - 1);
        return nums;
    }
};

class Solution {
    void maxHeapify(vector<int>& nums, int i, int len) {
        for (; (i << 1) + 1 <= len;) {
            int lson = (i << 1) + 1;
            int rson = (i << 1) + 2;
            int large;
            if (lson <= len && nums[lson] > nums[i]) {
                large = lson;
            } else {
                large = i;
            }
            if (rson <= len && nums[rson] > nums[large]) {
                large = rson;
            }
            if (large != i) {
                swap(nums[i], nums[large]);
                i = large;
            } else {
                break;
            }
        }
    }
    void buildMaxHeap(vector<int>& nums, int len) {
        for (int i = len / 2; i >= 0; --i) {
            maxHeapify(nums, i, len);
        }
    }
    void heapSort(vector<int>& nums) {
        int len = (int)nums.size() - 1;
        buildMaxHeap(nums, len);
        for (int i = len; i >= 1; --i) {
            swap(nums[i], nums[0]);
            len -= 1;
            maxHeapify(nums, 0, len);
        }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        heapSort(nums);
        return nums;
    }
};

class Solution {
    vector<int> tmp;
    void mergeSort(vector<int>& nums, int l, int r) {
        if (l >= r) return;
        int mid = (l + r) >> 1;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        int i = l, j = mid + 1;
        int cnt = 0;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                tmp[cnt++] = nums[i++];
            }
            else {
                tmp[cnt++] = nums[j++];
            }
        }
        while (i <= mid) {
            tmp[cnt++] = nums[i++];
        }
        while (j <= r) {
            tmp[cnt++] = nums[j++];
        }
        for (int i = 0; i < r - l + 1; ++i) {
            nums[i + l] = tmp[i];
        }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        tmp.resize((int)nums.size(), 0);
        mergeSort(nums, 0, (int)nums.size() - 1);
        return nums;
    }
};
